package middle;

import java.math.BigInteger;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * Description:
 * 请你来实现一个 atoi 函数，使其能将字符串转换成整数。
 *
 * 首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
 *
 * 如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
 * 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
 * 该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
 * 注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
 *
 * 在任何情况下，若函数不能进行有效的转换时，请返回 0 。
 *
 * @author: Faker
 * Date: 2020-11-09
 * Time: 16:09
 */
public class Code_8 {
    public static void main(String[] args) {
        Code_8 code_8 = new Code_8();
        String s = "-2000000000000000000000000000000000000000000000000000000000";
        int i = code_8.myAtoi(s);
        System.out.println(i);
    }

    /**
     * 解法一.正常遍历
     * 根据题目思路，我们先去掉空格，然后判断是否有正负号，利用flag标记，最后开始匹配数字并将数字记录在ans里面，并结合flag返回值；时间复杂度O（n），空间复杂度O（1）
     * 这里关于ans衍生出一个问题，如何处理越界问题：
     * 1.如果ans可以是long型，比较temp-1>INT_MAX即可，如同我在C++和python语言所体现的
     * 2.如果ans只能是int型，以结果为整数为列：如果有ans=ans10+pop，则比较ans10+pop>INT_MAX这里两边都不能溢出，乘10累计都可能溢出，我们需要反向思考变除变减比较，移项有
     * ans>(INT_MAX-pop)/10，但这个式子应该只在python中适用，因为他的除法是正常的，其他会向下取整，所以对于其他语言，可以对INT_MAX/10,再把pop单独拿出来讨论即可，如同我在java中体现的
     * @param str
     * @return
     */
    public int myAtoi(String str) {
        int i=0,n=str.length();
        while(i<n&&str.charAt(i)==' ')i++;
        if(i==n)return 0;
        int flag=1;
        if(str.charAt(i)=='+'||str.charAt(i)=='-'){
            if(str.charAt(i)=='-')flag=-1;
            i++;
        }
        int ans=0;
        while(i<n&&Character.isDigit(str.charAt(i))) {
            int temp=str.charAt(i)-'0';
            if (flag == 1 && (ans > Integer.MAX_VALUE / 10 || (ans == Integer.MAX_VALUE / 10 && temp > 7)))
                return Integer.MAX_VALUE ;
            //以正数为列，考虑稳大于和加temp才大于的情况
            if (flag == -1 && (ans > -(Integer.MIN_VALUE / 10) || (ans == -(Integer.MIN_VALUE / 10) && temp > 8)))
                return Integer.MIN_VALUE;
            ans=ans*10+temp;
            i++;
        }
        return ans*flag;
    }

    /**
     * 解法二.有限状态机
     * 在我理解正常遍历的方法只是适用于分支讨论较少的情况，不然代码就会显得很冗余，也很难思考。而有限状态机的关键在于我们的程序在每个时刻有一个状态 s，每次从序列中输入一个字符 c，并根据字符 c 转移到下一个状态 s'。这样，我们只需要建立一个覆盖所有情况的从 s 与 c 映射到 s' 的表格即可解决题目中的问题
     * https://leetcode-cn.com/problems/string-to-integer-atoi/solution/san-chong-fang-fa-zheng-chang-bian-li-you-xian-zhu/
     * @param str
     * @return
     */
    public int myAtoi1(String str) {
        Automata auto=new Automata();
        char[] temp=str.toCharArray();
        for(char c:temp)
            auto.get(c);

        return auto.sign*(int)auto.ans;
    }

    /**
     * 有限状态机
     */
    class Automata{
        private int state=0;
        private int[][] table={{0,1,2,3},{3,3,2,3},{3,3,2,3},{3,3,3,3}};
        long ans=0;
        int sign=1;

        public int gets(char c){
            if(c==' ')return 0;
            if(c=='+'||c=='-')return 1;
            if(Character.isDigit(c))return 2;
            return 3;
        }

        public void get(char c){
            state=table[state][gets(c)];
            if(state==2){
                ans=ans*10+(c-'0');
                ans= sign==1 ? Math.min(ans,Integer.MAX_VALUE):Math.min(ans,-(long)Integer.MIN_VALUE);
            }
            if(state==1&&c=='-')sign=-1;
        }

    }

    /***
     * 正则表达式解法
     * @param str
     * @return
     */
    public int myAtoi2(String str) {
        String pattern = "^\\s*([+-]?\\d+)";
        Pattern r = Pattern.compile(pattern);

        Matcher m = r.matcher(str);
        if (!m.find( ))  return 0;

        BigInteger ans = new BigInteger(m.group(1));
        if(ans.compareTo(new BigInteger(String.valueOf(Integer.MIN_VALUE)))<0){
            return Integer.MIN_VALUE;
        }
        if(ans.compareTo(new BigInteger(String.valueOf(Integer.MAX_VALUE)))>0){
            return Integer.MAX_VALUE;
        }
        return ans.intValue();

    }


}
